import Foundation
import GeekTime_PageSources


public struct Test_NodeList {
    
    
    
    // 反转链表
    public static func reverseList(_ list: NodeList) -> NodeList {
        
        var currentNode = list.head
        var previousNode: Node?
        var nextNode: Node?
        while currentNode != nil {
            // 取出next
            nextNode = currentNode?.next
            // 反转当前
            currentNode?.next = previousNode
            
            // 为下一轮循环准备
            previousNode = currentNode
            currentNode = nextNode
        }
        list.head = previousNode
        return list
    }
    
    
    // 链表成环
    public static func hasCycle(_ list: NodeList) -> Node? {
        //
        var slow = list.head
        var fast = list.head
        
        while fast != nil && fast?.next != nil {
            slow = slow?.next
            fast = fast?.next?.next
            
            // 有环
            if slow === fast {
                // 寻找环的入口
                
                // 1. 新指针移动到头结点
                var point = list.head
                while point !== slow {
                    // 2. 新指针和慢指针每次向后移动1个节点
                    point = point?.next
                    slow = slow?.next
                }
                // 直到他们相遇
                return point
            }
        }
        
        return nil
    }
    
}
